#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct node {
    char data;
    struct node *l, *r;
} node;

node *insert(node *root, int num) {
    if (root == NULL) {
        root = (node *) malloc(sizeof(node));
        root->data = 'A' + num;
        root->l = root->r = NULL;
        return root;
    }
    if (rand() % 2 == 0) {
        root->l = insert(root->l, num);
    } else {
        root->r = insert(root->r, num);
    }
    return root;
}

void p(node *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    p(root->l);
    p(root->r);
}

void m(node *root) {
    if (root == NULL) {
        return;
    }
    m(root->l);
    printf("%c ", root->data);
    m(root->r);
}

void b(node *root) {
    if (root == NULL) {
        return;
    }
    b(root->l);
    b(root->r);
    printf("%c ", root->data);
}

void q(node *root) {
    node *q[30];
    int front = 0, rear = 1;
    q[0] = root;
    while (front != rear) {
        node *t = q[front];
        front++;
        printf("%c ", t->data);
        if (t->l != NULL) {
            q[rear++] = t->l;
        }
        if (t->r != NULL) {
            q[rear++] = t->r;
        }
    }
}

//int main() {
//    node *root = NULL;
//    int n;
//    srand(time(0));
//    scanf("%d", &n);
//    for (int i = 0; i < n; ++i) {
//        root = insert(root, i);
//    }
//    p(root);
//    printf("\n");
//    m(root);
//    printf("\n");
//    b(root);
//    printf("\n");
//    q(root);
//    return 0;
//}